//
// Created by xili on 2024/9/20 20:16.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

//暴力递归
class Solution1 {
public:
    long long mostPoints(vector <vector<int>> &questions) {
        return f(questions, 0);
    }

    int f(vector <vector<int>> &q, int i) {
        if (i >= q.size()) {
            return 0;
        }
        //解决第i个问题
        int y = q[i][0] + f(q, i + q[i][1]);
        //不解决
        int n = f(q, i + 1);
        return max(y, n);
    }
};

//记忆化搜索
class Solution2 {
public:
    long long mostPoints(vector <vector<int>> &questions) {
        vector<long long> dp(questions.size() + 1, -1);
        return f(questions, 0, dp);
    }

    long long f(vector <vector<int>> &q, int i, vector<long long> &dp) {
        if (i >= q.size()) {
            return 0;
        }
        if (dp[i] != -1) {
            return dp[i];
        }
        //解决第i个问题
        long long y = q[i][0] + f(q, i + q[i][1] + 1, dp);
        //不解决
        long long n = f(q, i + 1, dp);
        dp[i] = max(y, n);
        return dp[i];
    }
};

//严格位置依赖
class Solution3 {
public:
    long long mostPoints(vector <vector<int>> &questions) {
        int n = questions.size();
        vector<long long> dp(n + 1);
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = max(dp[i + 1], questions[i][0] + dp[min(n, i + questions[i][1] + 1)]);
        }
        return dp[0];
    }
};